Performing software patching in large-scale cloud infrastructure systems presents significant challenges compared to that faced in corporate computing environments or smaller-scale data centers. For example, compared to many traditional corporate data center installations, cloud infrastructure environments often include many different types of computing systems utilizing hardware from many different vendors. Further, these heterogeneous server computers may execute a large number of different operating systems—each requiring different patches—that further may execute many different types and/or versions of applications (e.g., web server applications, database server applications, etc.) that similarly require different patches. Moreover, the application of these different patches may need to be performed according to particular orderings. Additionally, these operating systems and/or applications may require the use of application-specific update tools. Accordingly, keeping the large numbers of applications executing across a wide variety of operating systems and server computing devices effectively patched is a slow, difficult task.